#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_V 8 // 最大顶点数（A-H）

// 邻接表结点结构
typedef struct AdjListNode
{
    int vertex;
    struct AdjListNode *next;
} AdjListNode;

// 顶点结构
typedef struct
{
    char name;
    AdjListNode *head;
    int visited;
    int parent; // 记录生成树中的父结点
} Vertex;

// 图结构
typedef struct
{
    Vertex vertices[MAX_V];
    int vCount;
} Graph;

// 创建图
Graph *createGraph()
{
    Graph *g = (Graph *)malloc(sizeof(Graph));
    g->vCount = 0;
    return g;
}

// 添加顶点
void addVertex(Graph *g, char name)
{
    if (g->vCount >= MAX_V)
    {
        printf("Error: Graph is full\n");
        return;
    }
    g->vertices[g->vCount].name = name;
    g->vertices[g->vCount].head = NULL;
    g->vertices[g->vCount].visited = 0;
    g->vertices[g->vCount].parent = -1; // 初始化父结点为-1
    g->vCount++;
}

// 添加边（无向图）
void addEdge(Graph *g, int v1, int v2)
{
    if (v1 < 0 || v1 >= g->vCount || v2 < 0 || v2 >= g->vCount)
    {
        printf("Error: Invalid vertex index\n");
        return;
    }
    // 为v1添加v2邻接结点
    AdjListNode *newNode = (AdjListNode *)malloc(sizeof(AdjListNode));
    newNode->vertex = v2;
    newNode->next = g->vertices[v1].head;
    g->vertices[v1].head = newNode;
    // 为v2添加v1邻接结点
    newNode = (AdjListNode *)malloc(sizeof(AdjListNode));
    newNode->vertex = v1;
    newNode->next = g->vertices[v2].head;
    g->vertices[v2].head = newNode;
}

// 深度优先生成树（递归）
void DFSTree(Graph *g, int currentIndex)
{
    g->vertices[currentIndex].visited = 1;
    AdjListNode *node = g->vertices[currentIndex].head;
    while (node)
    {
        int adjVertex = node->vertex;
        if (!g->vertices[adjVertex].visited)
        {
            g->vertices[adjVertex].parent = currentIndex; // 设置父结点
            DFSTree(g, adjVertex);
        }
        node = node->next;
    }
}

// 打印生成树结构
void printTreeStructure(Graph *g)
{
    printf("DFS Spanning Tree Structure:\n");
    for (int i = 0; i < g->vCount; i++)
    {
        if (g->vertices[i].parent != -1)
        {
            printf("%c -> %c\n",
                   g->vertices[g->vertices[i].parent].name,
                   g->vertices[i].name);
        }
    }
}

// 销毁图
void destroyGraph(Graph *g)
{
    if (!g)
        return;
    for (int i = 0; i < g->vCount; i++)
    {
        AdjListNode *node = g->vertices[i].head;
        while (node)
        {
            AdjListNode *temp = node;
            node = node->next;
            free(temp);
        }
    }
    free(g);
}

int main()
{
    // 创建图
    Graph *g = createGraph();

    // 添加顶点（A-H）
    addVertex(g, 'A');
    addVertex(g, 'B');
    addVertex(g, 'C');
    addVertex(g, 'D');
    addVertex(g, 'E');
    addVertex(g, 'F');
    addVertex(g, 'G');
    addVertex(g, 'H');

    // 添加边（构建指定无向图）
    addEdge(g, 0, 1); // A-B
    addEdge(g, 0, 2); // A-C
    addEdge(g, 1, 3); // B-D
    addEdge(g, 2, 4); // C-E
    addEdge(g, 4, 5); // E-F
    addEdge(g, 4, 6); // E-G
    addEdge(g, 5, 6); // F-G
    addEdge(g, 6, 7); // G-H

    // 从A(0)开始生成深度优先生成树
    DFSTree(g, 0);

    // 打印生成树结构
    printTreeStructure(g);

    // 销毁图
    destroyGraph(g);
    return 0;
}